from typing import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n=len(nums)
        vist=[False]*n
        path=[]
        ans=[]
        # 问题： 当前层选哪一个元素 --》 遍历 选没有标记的
        def dfs(dep):
            # 结束条件，所有层已经选完
            if dep==n:
                ans.append(path.copy())
                return

            for i in range(n):
                if not vist[i]:
                    vist[i]=True
                    path.append(nums[i])
                    # 递归到下一层
                    dfs(dep+1)
                    # 回溯
                    vist[i]=False
                    path.pop()
        dfs(0)
        return ans